/*
 * P1678 烦恼的高考志愿
 * https://www.luogu.com.cn/problem/P1678
 */

#include <iostream>

using namespace std;

int jisuanBumanyidu(int fenshuxian[], int m, int gufen) {
    int zuo = 0; //初始在数组的最左边，0
    int you = m - 1; //初始在数组最右边，即，总长度-1
    int zhong; //二分的位置游标

    while (zuo <= you) {
        zhong = (zuo + you) / 2;
        int dangqianFenshuxian = fenshuxian[zhong];

        // 打印一些中间信息
        cout << "Search: zuo=" << zuo << ", zhong=" << zhong << ", you=" << you << ", dangqianFenshuxian="
             << dangqianFenshuxian
             << endl;

        if (dangqianFenshuxian == gufen) {
            cout << "找到了与当前估分" << gufen << "相等的分数线=" << dangqianFenshuxian << endl;
            break;
        } else if (dangqianFenshuxian < gufen) {
            zuo = zhong + 1;
        } else {
            you = zhong - 1;
        }
    }

    if (zuo <= you) {
        // 第一种情况，说明找到了与估分相等的分数线，所以 不满意度为 0
        return 0;
    } else if (zuo >= 0 && zuo < m && you >= 0 && you < m) {
        // 第二种情况，说明，没有找到完全相等的分数线，但是，分数是介于 fenshuxian 数组最小值和最大值之间的数
        return min(abs(gufen - fenshuxian[zuo]), abs(gufen - fenshuxian[you]));
    } else {
        // 第二种情况，gufen 比 fenshuxian 中的最小值还小，或者比最大值还大，
        // 这个时候 zhong 一定是移动到了 最左边，或最右边 的元素，所以
        return abs(gufen - fenshuxian[zhong]);
    }
}

int main() {
    // 忽略了从 cin 中输入数据的步骤
    int m = 4;
    int n = 3;
    int fenshuxian[] = {513, 598, 567, 689}; // 学校分数线
    int xueshengGufen[] = {500, 600, 550}; // 学生估分

    // 给分数线排序
    sort(fenshuxian, fenshuxian + m);

    int zongBumanyidu = 0;

    for (int i = 0; i < n; i++) {
        int gufen = xueshengGufen[i];
        int bumanyidu = jisuanBumanyidu(fenshuxian, m, gufen);

        zongBumanyidu += bumanyidu;
    }

    cout << "总不满意度=" << zongBumanyidu << endl;

    return 0;
}